package org.czl.leetcode4;

import java.util.*;

public class l684 {
    //基环树模版
    public static void main(String[] args) {
        //[1,2], [2,3], [3,4], [1,4], [1,5]
        System.out.println(Arrays.toString(findRedundantConnection(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}})));

    }
    public static int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] in = new int[n + 1];
        List<Integer>[] pa = new ArrayList[n + 1];
        for(int i = 0; i < n + 1; i++){
            pa[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int x = edge[0]; int y = edge[1];
            in[x]++;
            in[y]++;
            pa[x].add(y);
            pa[y].add(x);
        }
        Deque<Integer> queue = new LinkedList<>();
        for(int i = 0; i < n + 1; i++){
            if(in[i] == 1){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            int cur = queue.poll();
            for(int i : pa[cur]){
                in[i]--;
                in[cur]--;
                if(in[i] == 1){
                    queue.add(i);
                }
            }
        }
        for(int i = n - 1; i >= 0; i--){
            int[] e = edges[i];
            int x = e[0]; int y = e[1];
            if((in[x] >= 2 && in[y] >= 1) || ( in[x] >=1 && in[y] >= 2)){
                return new int[]{x,y};
            }
        }
        return new int[]{-1, -1};
    }
}
